[BZOJ2688]Green Hackenbush

Posted on Edited on In

[BZOJ2688]Green Hackenbush

题意: 有 \(n\) 棵随机的二叉树，每棵只知道大小为 \(a_i\)

博弈:每次选取一个子树删掉，只剩根不能操作，求先手获胜概率

考虑这个博弈，求出一棵树的 \(\text{SG}\) 值

显然有:

1.只有一个点的树的 \(\text{SG}\) 值为0

2.多个树组合的问题为 \(\text{SG}\) 值异或

暴力 \(dp\) ，对于树 \(T\) 求答案，设 \(T\) 所有可行的后继状态集合为 \(N(T)\) ，则得到 \(\text{SG}\) 值的表达式为

\(\text{SG}(T)=\text{mex}_{R\in N(T)}\lbrace\text{SG(R)}\rbrace\)

直接求解复杂度过高，考虑归纳性质

性质:

1.一棵根节点只有一个儿子的树，其 \(\text{SG}\) 值为儿子的 \(\text{SG}\) 值+1

考虑归纳证明:

设子树为 \(T\) ，令 \(T+u\) 表示 \(T\) 子树上面接上自己作为根，问题变为求证 \(\text{SG}(T+u)=\text{SG}(T)+1\)

设已经归纳证明所有 \(T\) 的子联通块成立

我们要求 \(\text{SG}(T+u)\)

\(\text{SG}(T+u)=\text{mex}\{\text{SG}(u),\forall _{R\in N(T)}\text{SG}(R+u)\}\)

由归纳的性质有

\(\forall _{R\subsetneq T}\text{SG}(R+T)=\text{SG}(R)+1\)

又因为 \(\text{SG}(u)=0\) ，看做把所有儿子的情况平移了1，0的位置由自己占据，因而上式成立

2.多叉树的问题可以归纳为 根分别接上每个儿子得到的树 的问题的组合

因为儿子之间实际互不干扰，比较容易理解

由此得到，一棵树的 \(\text{SG}\) 值为其所有儿子的 \(\text{SG}\) 值+1的异或和

令 \(dp_{n,i}\) 为一棵 \(n\) 个节点的二叉树 \(\text{SG}\) 值为 \(i\) 的概率，为了便于转移，设空树的 \(\text{SG}\) 值为-1

考虑直接枚举两棵子树的大小和 \(\text{SG}\) 值

考虑对于 \(n\) 个节点的二叉树，设其左儿子为 \(i\) 时的总概率为 \(F_i\)

得到的 \(\text{dp}\) 转移是

\(dp_{n,(a+1)\oplus (b+1)}\leftarrow {dp_{i,a}\cdot dp_{n-i-1,b}\cdot F_i}\)

我们知道 \(n\) 个节点的二叉树方案数为 \(Catalan(n)=\frac{(2n)!}{n!(n+1)!}\)

由此得到 \(\begin{aligned} F_i=\frac{Catalan(i)Catalan(n-i-1)}{Catalan(n)}\end{aligned}\)

此题范围可以直接带入 \(Catalan(i)\) 求解，但是依然要提一下递推的做法（似乎精度更有保障?）

\(\begin{aligned} F_i=\frac{\frac{(2i)!}{i!(i+1)!}\cdot \frac{(2n-i-2)!}{(n-i-1)!(n-i)!}}{\frac{(2n)}{n!(n+1)!}}\end{aligned}\)

递推求解 \(F_i\) ，每次 \(i\) 改变一阶乘只会改变1或者2，因此由 \(F_{i-1}\) 得到 \(F_i\) 的递推式为

\(F_i=\left\{ \begin{aligned}\frac{n(n+1)}{2n(2n-1)}&& i=0\\ F_{i-1}\cdot \frac{2i(2i-1)}{(i+1)i}\frac{(n-i+1)(n-i)}{2(n-i)(2n-2i-1)} && i\in[1,n-1]\end{aligned}\right.\)

化简之后应该是

\(F_i=\left\{ \begin{aligned}\frac{(n+1)}{2(2n-1)}&& i=0\\ F_{i-1}\cdot \frac{(2i-1)}{(i+1)}\frac{(n-i+1)}{(2n-2i-1)} && i\in[1,n-1]\end{aligned}\right.\)

至此得到一个朴素的 \(O(n^4)\) 预处理，由于是异或，可以用 \(\text{FWT}_{\oplus}\) 求解，复杂度为 \(O(n^3)\)

对于输入的每棵树，类似背包地叠加概率即可，复杂度为 \(O(n^3)\)

以下是朴素dp代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include<bits/stdc++.h>
using namespace std;
typedef double db;
#define rep(i,a,b) for(reg int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(reg int i=a,i##end=b;i>=i##end;--i)

char IO;
template <class T=int> T rd(){
	T s=0; int f=0;
	while(!isdigit(IO=getchar())) if(IO=='-') f=1;
	do s=(s<<1)+(s<<3)+(IO^'0');
	while(isdigit(IO=getchar()));
	return f?-s:s;
}

const int N=128;

int n;
db dp[N][N];

void FWT(db *a,int f){
	for(int i=1;i<N;i<<=1){
		for(int l=0;l<n;l+=i*2) {
			for(int j=l;j<l+i;j++){
				db t=a[j+i];
				a[j+i]=a[j]-t;
				a[j]+=t;
			}
		}
	}
	if(f==-1) rep(i,0,N-1) a[i]/=N;
}

db F[N],G[N];

int main(){
	dp[0][0]=1,dp[1][0]=1;
	rep(i,2,100) {
		F[0]=1.0/(2*i)/(2*i-1)*(i+1)*i;
		rep(j,1,i-1) {
			F[j]=F[j-1] *  (2*j)*(2*j-1)/(j+1)/j   * 1.0/(2*(i-j))/(2*(i-j)-1)*(i-j+1)*(i-j);
		}
		rep(a,0,i-1) rep(h1,0,N-1) if(dp[a][h1]>0) {
			rep(h2,0,N-1) if(dp[i-a-1][h2]) {
				int nxt=0;
				if(a>0) nxt^=h1+1;
				if(i-1-a>0) nxt^=h2+1;
				dp[i][nxt]+=dp[a][h1]*dp[i-a-1][h2]*F[a];
			}
		}
	}
	n=rd();
	rep(i,0,N-1) F[i]=0;
	F[0]=1;
	rep(i,1,n) {
		int x=rd();
		rep(j,0,N-1) G[j]=0;
		rep(j,0,N-1) if(F[j]) rep(k,0,N-1) G[j^k]+=F[j]*dp[x][k];
		rep(j,0,N-1) F[j]=G[j];
	}
	db ans=0;
	rep(i,1,N-1) ans+=F[i];
	printf("%.6lf\n",ans);
}


以下是FWT优化代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include<bits/stdc++.h>
using namespace std;
typedef double db;
#define rep(i,a,b) for(reg int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(reg int i=a,i##end=b;i>=i##end;--i)

char IO;
template <class T=int> T rd(){
	T s=0; int f=0;
	while(!isdigit(IO=getchar())) if(IO=='-') f=1;
	do s=(s<<1)+(s<<3)+(IO^'0');
	while(isdigit(IO=getchar()));
	return f?-s:s;
}

const int N=128;

int n;
db dp[N][N],T[N][N];

void FWT(db *a,int f){
	for(int i=1;i<N;i<<=1){
		for(int l=0;l<N;l+=i*2) {
			for(int j=l;j<l+i;j++){
				db t=a[j+i];
				a[j+i]=a[j]-t;
				a[j]+=t;
			}
		}
	}
	if(f==-1) rep(i,0,N-1) a[i]/=N;
}

db F[N],G[N];

int main(){
	dp[0][0]=1,dp[1][0]=1;
	T[0][0]=1,T[1][1]=1;
	FWT(T[0],1),FWT(T[1],1);

	rep(i,2,100) {
		F[0]=1.0/(2*i)/(2*i-1)*(i+1)*i;
		rep(j,1,i-1) {
			F[j]=F[j-1] *  (2*j)*(2*j-1)/(j+1)/j   * 1.0/(2*(i-j))/(2*(i-j)-1)*(i-j+1)*(i-j);
		}
		rep(j,0,i-1) rep(k,0,N-1) dp[i][k]+=T[j][k]*T[i-j-1][k]*F[j];
		FWT(dp[i],-1);
		rep(j,0,N-2) T[i][j+1]=dp[i][j];
		FWT(T[i],1);
	}
	n=rd();
	rep(i,0,N-1) F[i]=0;
	F[0]=1;
	rep(i,1,n) {
		int x=rd();
		rep(j,0,N-1) G[j]=0;
		rep(j,0,N-1) if(F[j]) rep(k,0,N-1) G[j^k]+=F[j]*dp[x][k];
		rep(j,0,N-1) F[j]=G[j];
	}
	db ans=0;
	rep(i,1,N-1) ans+=F[i];
	printf("%.6lf\n",ans);
}